#include <fstream>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
struct xy{
    int x;
    int y;
    int t;
};
#define max_N 305
#define max_M 305

#define min(a,b) ((a<b)?a:b)
int score[max_N][max_M];
int flag[max_N][max_M];
int max_time = 1001;

int dx[5] = {0,-1, 0, 0, 1};
int dy[5] = {0,0, -1, 1, 0};

bool judge(int x, int y)
{
    if (x<0||y<0||x>=max_N||y>=max_M)
        return false;
    return true;
}

int bfs()
{
    int result = max_time+10;
    xy begin;
    begin.x = 0;
    begin.y = 0;
    begin.t = 0;
    queue<xy> temp_pro;
    temp_pro.push(begin);
    // 开始就炸死
    if (score[0][0]==0)
        return -1;
    while(temp_pro.size()){
        xy temp = temp_pro.front();
        temp_pro.pop();
        for (int i = 1; i < 5;++i){
            int x = temp.x + dx[i];
            int y = temp.y + dy[i];
            int t = temp.t + 1;
            if (!judge(x,y))
                continue; 
            // 炸弹碰不到的地方
            if (score[x][y] == -1){
                return min(result, t);
            }
            if (t>= score[x][y])
                continue;
            if (flag[x][y]>0)
                continue;
            flag[x][y] = 1;
            xy begin;
            begin.x = x;
            begin.y = y;
            begin.t = t;
            temp_pro.push(begin);
            
        }
    }
    if (result>=max_time)
        return -1;
    else
        return result;
}
int main()
{
    //fstream cin("test.txt");
    int n;
    while(cin>>n){
        if (n<=0)
            continue;
        memset(score,-1,sizeof(score));
        memset(flag,-1,sizeof(flag));
        for (int i = 0; i < n;++i){
            int x, y,t;
            cin >> x >> y >> t;
            for (int j = 0; j < 5;++j){
                if (judge(x+dx[j],y+dy[j])){
                    int temp = score[x + dx[j]][y + dy[j]];
                    if (temp==-1)
                        score[x + dx[j]][y + dy[j]] = t;
                    else
                        score[x + dx[j]][y + dy[j]] = temp < t ? temp : t;
                }
            }
        }
        cout<<bfs()<<endl;
    }
    return 0;
}